package com.atguigu.heap;

import com.atguigu.array.Array;

public class MinHeap<E extends Comparable<E>> {
    private Array<E>data;
    public MinHeap(){
        data=new Array<>();
    }
    //将数组调整成最小堆
    public MinHeap(E[]data){
        for (int i = parent(data.length - 1); i >=0; i--) {
            siftDown(i);
        }
        this.data=new Array<>(data);
    }
    //取出堆中的最小元素，并且替换成元素e
    public void replace(E e){
        E ret=data.get(0);
        data.set(0,e);
        siftDown(0);
    }
    //得到堆中最小的元素
    public E findMin(){
        if(data.getSize() == 0)
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        return data.get(0);
    }
    //取出堆中最小的元素
    public E extractMin(){
        E e = findMin();
        data.swap(0,data.getSize()-1);
        data.removeLast();
        siftDown(0);
        return e;
    }
    // 返回一个布尔值, 表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }
    // 返回堆中的元素个数
    public int size(){
        return data.getSize();
    }
    //向堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }
    //下沉
    private void siftDown(int k){
        while(leftChild(k)<data.getSize()){
            int j=leftChild(k);
            if(j+1<data.getSize()&&data.get(j+1).compareTo(data.get(j))<0){
                j=j+1;
            }
            if(data.get(k).compareTo(data.get(j))<=0){
                break;
            }
            data.swap(k,j);
            k=j;
        }
    }
    //上浮
    private void siftUp(int k){
        while(k>0&&data.get(k).compareTo(data.get(parent(k)))<0){
            data.swap(k,parent(k));
            k=parent(k);
        }
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        return (index-1)/2;
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index*2+1;
    }
    //返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index*2+2;
    }
}
